package class03;

import java.util.Stack;

/**
 * 非递归方式实现 先序 中序 后序
 * 递归都可以通过非递归的方式实现
 */
public class Code02_UnRecursiveTraversalBT {
    static class Node {
        int value;
        Node left;
        Node right;

        Node(int value) {
            this.value = value;
        }
    }

    static void pre(Node node) {
        if (null == node) {
            return;
        }

        Stack<Node> stack = new Stack<>();


        stack.push(node);

        while (!stack.isEmpty()) {

            Node cur = stack.pop();
            System.out.print(cur.value + " ");

            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }

    }

    static void in(Node cur) {


        if (cur != null) {
            Stack<Node> stack = new Stack<Node>();
            while (!stack.isEmpty() || cur != null) {
                if (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                } else {
                    cur = stack.pop();
                    System.out.print(cur.value + " ");
                    cur = cur.right;
                }
            }
        }
        System.out.println();

    }


    static void pos1(Node node) {
        if (null != node) {
            Stack<Node> s1 = new Stack<>();
            Stack<Node> s2 = new Stack<>();

            s1.push(node);

            while (!s1.isEmpty()) {
                Node cur = s1.pop();
                s2.push(cur);

                if (cur.left != null) {
                    s1.push(cur.left);
                }
                if (cur.right != null) {
                    s1.push(cur.right);
                }
            }
            while (!s2.isEmpty()) {
                System.out.print(s2.pop().value + " ");
            }

        }
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        head.right.right = new Node(7);

        pre(head);
        System.out.println("========");
        in(head);
        System.out.println("========");
        pos1(head);
        System.out.println("========");

    }
}
